[QSP / QSVT] QSVT 應用：解線性系統

2023 iThome 鐵人賽

DAY 17

自我挑戰組

不嚴謹的量子計算雜談系列第 17 篇

15th鐵人賽量子計算

bwl

2023-09-26 08:32:34

307 瀏覽

分享至

給定一可逆矩陣 $A$ 以及一向量 $|b\rangle$ ，我們想找出 $|x\rangle = A^{-1}|b\rangle$ ；這就是我們今天要解決的線性系統 (linear system) 問題。在量子計算的領域，線性系統問題稱為 Quantum Linear System Problem (QLSP)，與古典的線性系統問題稍有差異，有興趣的讀者可以翻閱 QCnote 第十章。

HHL 是最早且廣為人知的解決 QLSP 的演算法；今天，我們要探討的則是基於 QSVT 的另類演算法，其與 HHL 各有優劣，讓我們繼續看下去。

QLSP 的問題核心在於準備 $A^{-1}$ 的量子電路，接著只要再將 $A^{-1}$ 應用在初始量子態 $|b\rangle$ 上即大功告成。那麼，逆矩陣和奇異值有什麼關係？令 $A = W\Sigma V^\dagger$ 為 $A$ 的 SVD，則 $A^\dagger = V\Sigma^\dagger W$ 且 $A^{-1} = V\Sigma^{-1}W^\dagger$ (因為 $V$ 和是么正矩陣，所以 $V^\dagger = V^{-1}$ ， $W$ 亦同)。由於 $\Sigma$ 是實對角矩陣，所以 $\Sigma^\dagger = \Sigma$ 且 $\Sigma^{-1}$ 僅是將主對角線上的元素取倒數！換句話說，若

$A^\dagger = \sum_k \sigma_k|v_k\rangle\langle w_k|,$

則

$A^{-1} = \sum_k {1\over \sigma_k}|v_k\rangle\langle w_k|.$

看出來了嗎？我們只需對 $A^\dagger$ 的奇異值做 $P(x)\approx 1/x$ 的多項式轉換，就能得到 $A^{-1}$ ！若 $A$ 不可逆，上述的手法也可以用在計算偽逆矩陣 (pseudoinverse matrix)。

HHL 的一大缺點在於，由於計算過程需要 QPE，因此所需 qubit 數量多 (隨精確度增加)。相對的，基於 QSVT 的解法只需約略與矩陣大小相當的量子暫存器，但是電路深度卻隨著精確度提高：精確度來自多項式 $P(x)$ 逼近 $1/x$ 的次數 (degree)，次數越高結果越精確，但深度也隨之增加！很不幸的，對 NISQ 時期的量子電腦而言，上百個量子閘的深度已經是極限了，但此 QSVT 方法的電路深度動輒數千，因此現階段難以實現！